8.7 Reequilibrados en árboles AVL  

Cada vez que insertemos o eliminemos un nodo en un árbol AVL pueden suceder dos cosas: que el árbol se mantenga como AVL o que pierda esta propiedad. En el segundo caso siempre estaremos en uno de los explicados anteriormente, y recuperaremos el estado AVL aplicando la rotación adecuada.

Ya comentamos que necesitamos añadir un nuevo miembro a cada nodo del árbol para averiguar si el árbol sigue siendo AVL, el Factor de Equilibrio. Cada vez que insertemos o eliminemos un nodo deberemos recorrer el camino desde ese nodo hacia el nodo raíz actualizando los valores de FE de cada nodo. Cuando uno de esos valores sea 2 ó -2 aplicaremos la rotación correspondiente.

Debido a que debemos ser capaces de recorrer el árbol en dirección a la raíz, añadiremos un nuevo puntero a cada nodo que apunte al nodo padre. Esto complicará algo las operaciones de inserción, borrado y rotación, pero facilita y agiliza mucho el cálculo del FE, y veremos que las complicaciones se compensan en gran parte por las facilidades obtenidas al disponer de este puntero.

Nota: En rigor, no es necesario ese puntero, podemos almacenar el camino que recorremos para localizar un nodo concreto usando una pila, y después podemos usar la pila para recuperar el camino en orden inverso. Pero esto nos obliga a introducir otra estructura dinámica, y según mi opinión, complica en exceso el algoritmo.

Cuando estemos actualizando los valores de FE no necesitamos calcular las alturas de las dos ramas de cada nodo, sabiendo en valor anterior de FE, y sabiendo en qué rama hemos añadido o eliminado el nodo, es fácil calcular el nuevo valor de FE. Si el nodo ha sido añadido en la rama derecha o eliminado en la izquierda, y ha habido un cambio de altura en la rama, se incrementa el valor de FE; si el nodo ha sido añadido en la rama izquierda o eliminado en la derecha, y ha habido un cambio de altura en la rama, se decrementa el valor de FE.

Los cambios de altura en una rama se producen sólo cuando el FE del nodo raíz de esa rama ha cambiado de 0 a 1 ó de 0 a -1. En caso contrario, cuando el FE cambia de 1 a 0 ó de -1 a 0, no se produce cambio de altura.

Si no hay cambio de altura, los valores de FE del resto de los nodos hasta el raíz no pueden cambiar, recordemos que el factor de equilibrio se define como la diferencia de altura entre las ramas derecha e izquierda de un nodo, la altura de la rama que no pertenece al camino no puede cambiar, puesto que sigue teniendo los mismos nodos que antes, de modo que si la altura de la rama que pertenece al camino no cambia, tampoco puede cambiar el valor de FE.

Por ejemplo, supongamos que en siguiente árbol AVL insertamos el nodo de valor 8:

Para empezar, cualquier nodo nuevo será un nodo hoja, de modo que su FE será siempre 0.

Ahora actualizamos el valor de FE del nodo padre del que acabamos de insertar (P). El valor previo es 0, y hemos añadido un nodo en su rama izquierda, por lo tanto, el nuevo valor es -1. Esto implica un cambio de altura, por lo tanto, continuamos camino hacia la raíz.

A continuación tomamos el nodo padre de P (Q), cuyo valor previo de FE era 1, y al que también hemos añadido un nodo en su rama izquierda, por lo tanto decrementamos ese valor, y el nuevo será 0. En este caso no ha incremento de altura, la altura del árbol cuya raíz es Q sigue siendo la misma, por lo tanto, ninguno de los valores de FE de los nodos hasta el raíz puede haber cambiado. Es decir, no necesitamos seguir recorriendo el camino.

Si verificamos el valor de FE del nodo R vemos que efectivamente se mantiene, puesto que tanto la altura del subárbol derecho como del izquierdo, siguen siendo las mismas.

Pero algunas veces, el valor de FE del nodo es -2 ó 2, son los casos en los que perdemos la propiedad AVL del árbol, y por lo tanto tendremos que recuperarla.

Reequilibrados en árboles AVL por inserción de un nodo

En ese caso, cuando el valor de FE de un nodo tome el valor -2 ó 2, no seguiremos el camino, sino que, con el valor de FE de el nodo actual y el del nodo derecho si FE es 2 o el del nodo izquierdo si es -2, determinaremos qué tipo de rotación debemos hacer.

FE nodo actual	FE del nodo derecho	FE del nodo izquierdo	Rotación
-2	No importa	-1	RSD
-2	No importa	1	RDD
2	-1	No importa	RDI
2	1	No importa	RSI

El resto de los casos no nos interesan. Esto es porque en nodos desequilibrados hacia la derecha, con valores de FE positivos, siempre buscaremos el equilibrio mediante rotaciones a la izquierda, y viceversa, con nodos desequilibrados hacia la izquierda, con valores de FE negativos, buscaremos el equilibrio mediante rotaciones a la derecha.

Supongamos que el valor de FE del nodo ha pasado de -1 a -2, debido a que se ha añadido un nodo. Esto implica que el nodo añadido lo ha sido en la rama izquierda, si lo hubiéramos añadido en la derecha el valor de FE nunca podría decrecer.

Reequilibrados en árboles AVL por borrado de un nodo

Cuando el desequilibrio se debe a la eliminación de un nodo la cosa puede ser algo diferente, pero veremos que siempre se puede llegar a uno de los casos anteriores.

Supongamos el siguiente ejemplo, en el árbol AVL eliminaremos el nodo de valor 3:

El valor de FE del nodo P pasa de 1 a 2, sabemos que cuando el valor de FE de un nodo es 2 siempre tenemos que aplicar una rotación a izquierdas. Para saber cual de las dos rotaciones debemos aplicar miramos el valor de FE del nodo derecho. Pero en este caso, el valor de FE de ese nodo es 0. Esto no quiere decir que no podamos aplicar ninguna de las rotaciones, por el contrario, podremos aplicar cualquiera de ellas. Aunque por economía, lo razonable es aplicar la rotación simple.

Si aplicamos la rotación simple, el resultado es:

Y aplicando la rotación doble:

Del mismo modo, el valor de FE del nodo derecho podría haber sido 1 ó -1, en ese caso sí está determinado el tipo de rotación a realizar.

El razonamiento es similar cuando se eliminan nodos y el resultado es que se obtiene un nodo con FE de -2, en este caso se realizará una rotación a derechas, y la rotación dependerá del valor de FE del nodo izquierdo al que muestra el desequilibrio. Si es 0 ó -1 haremos una rotación simple, si es 1, haremos una rotación doble.

Tendremos entonces una tabla más general para decidir la rotación a aplicar:

FE nodo actual	FE del nodo derecho	FE del nodo izquierdo	Rotación
-2	No importa	-1	RSD
-2	No importa	0	RSD
-2	No importa	1	RDD
2	-1	No importa	RDI
2	0	No importa	RSI
2	1	No importa	RSI

Los árboles AVL siempre quedan equilibrados después de una rotación.

Esto puede comprobarse analizando los métodos de rotación que hemos estudiado, después de efectuada la rotación, la altura del árbol cuya raíz es el nodo rotado se mantiene, por lo tanto, no necesitamos continuar el camino hacia la raíz: sabemos que el árbol es AVL.